This invention relates generally to the field of integrated circuit design and more specifically to a methodology for meeting timing constraints in the design of digital circuits.
In designing electronic circuits and systems, computer-automated design systems are used for defining and verifying various prototype circuit configurations. As part of the circuit definition, delay constraints are specified by the circuit designer. These delay constraints should be satisfied when the prototype circuit is fabricated.
In conventional approaches to circuit design, the following steps are typically performed:
(1) the load capacitance for each cell in the circuit is estimated using a fanout-based model;
(2) the size of each cell is set to optimize timing of the circuit;
(3) the cells are placed, and the net (wire) lengths of the circuit are estimated;
(4) the wires are routed; and
(5) final analysis is made to determine whether timing closure (i.e., satisfaction of timing constraints) is achieved.
In step (2), the sizes of cells within the circuit are chosen and held constant once chosen. The placement algorithm used thereafter will assign different net lengths between cells, and these lengths have conventionally been difficult to predict prior to placement. While net lengths have been estimated prior to placement by use of an estimation function or table which gives the load value of a net based on the number of fanout gates, this estimation function is usually inaccurate. This difficulty in accurately predicting net lengths leads to unpredictable delay effects after cell placement occurs. For example, some nets turn out to be longer in length than expected. These longer nets cause longer delays which prevent satisfaction of timing constraints in the digital circuit. Thus, under the conventional design approach, timing closure is not certain until after placement.
Failure to achieve timing closure after placement leads to additional expenses and other problems for the designer. To correct for failure to achieve timing closure, the designer has the option of fixing the design manually, which is difficult and time consuming because the automatically optimized digital network is not easy to understand. As a second option, the designer may change the Hardware Description Language (HDL) specification and repeat the design process. However, timing closure will again not be certain until after placement. Thus, the design process must again be repeated before the designer can determine if the HDL specification changes were successful in enabling timing closure.
A common method for dealing with inaccurate net load estimates is by estimating the net load at a considerably larger value than typically estimated. Although this method increases the probability of meeting timing constraints after placement, it causes the sizes of the gates to be considerably larger than necessary. Gates which are larger than the necessary size are wasteful in both silicon area and power consumption. This leads to chips which are larger, more expensive to produce, and use more electrical power than necessary.
Another problem with the conventional circuit design approach concerns the timing analysis required during optimization and during placement. The timing analysis performed throughout the conventional circuit design process is very time consuming, and accounts for most of the run time of a conventional circuit design system.
A further disadvantage of the conventional design approach relates to the net length modifications performed by the placement program. Depending on the location chosen for each gate, each net length may be modified. As each net length is modified, the capacitive load of the net will change. As a result, the delays of the gates driving the net will change. Therefore, the delays, which were carefully optimized during the logic design, are very different in value after cell placement, thereby contributing to poor network optimization.
Additionally, most of the progress in the state of the art for digital circuit design can be characterized as increased integration which has led to increasingly complex software systems which are slow, and difficult to design and maintain.
A further disadvantage with conventional design approaches is in the difficulty of iterating between placement and sizing, since the logic synthesis program is often operated by the logic designer who also wrote the HDL specification, but the placement program is often operated by the silicon chip manufacturer, after the design is complete.
One proposal has been made to keep delay constant while expressing size as a linear function of the gate load. See, J. Grodstein, E. Lehman, H. Harkness, B. Grundmann, and Y. Watanabe, xe2x80x9cA Delay Model for Logic Synthesis of Continuously-Sized Networksxe2x80x9d, Digest Int. Conf. On Computer Aided Design, pp. 458-462, San Jose, Calif. Nov. 5-9, 1995. Under this proposal, as the gate load changes, the gate size automatically grows sufficiently to hold the delay constant.
The constant delay model has been proposed in a mapping algorithm. See, E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, xe2x80x9cLogic Decomposition During Technology Mappingxe2x80x9d, Digest Int. Conf. On Computer Aided Design, pp. 264-271, San Jose, Calif. Nov. 5-9, 1995. However, this proposal does not provide a good method for choosing the constant delays and, in addition, it only applies the constant delay model to mapping.
Similarly, the constant delay model is proposed for fanout optimization. See, K. Kodandapani, J. Grodstein, A. Domic, and H. Touati, xe2x80x9cA Simple Algorithm For Fanout Optimization Using High Performance Buffer Librariesxe2x80x9d, Digest Int. Conf. On Computer Aided Design, pp. 466-471, Santa Clara, Nov. 7-11, 1993. While the above-mentioned references note the importance of the constant delay model, they do not note the importance of gain, also termed xe2x80x9celectrical effortxe2x80x9d.
In Sutherland and R. Sproull, xe2x80x9cThe Theory of Logical Effort: Designing for Speed on the Back of an Envelopexe2x80x9d, Advanced Research in VLSI, pp. 3-16, University of California, Santa Cruz, 1991, the delay is noted as being dependent on gain. A size independent formulation of the delay optimization problem is also presented, but the solution is intended for use as imprecise, scratch-pad type calculations, and not part of an overall integrated, automated solution to cell placement in the design of integrated circuits. In V. Kumar, xe2x80x9cGeneralized Delay Optimization of Resistive Interconnections Through an Extension of Logical Effort, Proc. Int. Symp. On Circuits and Systems, 1993, vol. 3, pp. 2106-2109, Chicago, Ill., May 3-6, 1993, the methods above are used to analyze long wires with a significant amount of RC delay.
In U.S. Pat. No. 5,654,898, a method and apparatus for determining an integrated circuit layout is shown and described whereby timing-driven buffer sizing is performed to satisfy timing requirements. However, this solution also relies on imprecise calculations and does not teach or suggest an overall integrated, automated solution to cell placement in the design of integrated circuits.
What is needed and what has been invented is a method and apparatus for overcoming the foregoing deficiencies, and for maintaining timing closure upon placement and routing of the digital circuit or network.
The present invention broadly provides a method for designing an integrated circuit layout based upon an electronic circuit description and by using a cell library containing cells that each have an associated relative delay value, comprising the steps of:
(a) selecting a plurality of cells that are intended to be coupled to each other with a plurality of wires and that can be used to implement the digital circuit based on the electronic circuit description;
(b) determining an initial intended location of each of the selected plurality of cells on the integrated circuit, the step of determining the initial intended location of each of the selected plurality of cells including the step of determining an initial intended area of each of the selected plurality of cells, the initial intended area of at least some of the selected plurality of cells being determined using the associated relative delay value of the selected cell and the initial intended lengths of some of the wires coupled to the selected cell;
(c) finalizing the location and area of each of the selected plurality of cells and the lengths of the wires; and
(d) routing the digital circuit to generate the integrated circuit layout using the finalized location and area of each of the selected plurality of cells and the finalized wire lengths.
The present invention makes possible an advantage of facilitating the maintenance of timing closure throughout the design process. The invention makes possible another advantage of compensating for the unpredictable delay effects due to the placement and routing steps in the design process.
Still another advantage made possible by the invention is the avoidance of costly timing analysis of conventional approaches. In contrast, timing analysis is required during placement and throughout the conventional design process.
The following are also made possible by the invention by establishing circuit area, instead of timing, as an optimization objective. First, excess circuit area which is formed in one module can be compensated in another module. In contrast, excess timing in one module cannot generally be compensated by another module. Second, area is a measurable parameter when comparing two different circuits. In contrast, it is difficult to compare two circuits for performance advantages, based on timing, since timing may be different for every circuit path. Third, if circuit area is established as a constraint, then routing completion is not guaranteed to be achieved.